/*  Estevão Becker Konecsni - FIAP - 2013
	E-mail: icmp.request@gmail.com
	Estrutura de Dados II - Métodos de Ordenação e Busca
	Utilizando: Vetores
	Ferramentas Utilizadas: gedit, xterm e gcc 4.6.3 (glibc 2.15)
	Versão: 2013-12-04 */
	
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// windows.h ou linux.h:
#include "linux.h"

// Tamanho máximo do vetor:
#define MAX 30

// Variáveis Globais:
int vetor[MAX];
int tamanho; // Tamanho dado pelo usuário
int ordenado = 0; // Controle true ou false se o vetor está ordenado (verificação = busca binária)
int quick = 0; // Controle se Insertion Sort está sendo chamado via Quick Sort ou não


/* Declaração de Funções */

// Vetor:
void criar_vetor_aleatorio();
void criar_vetor_manual();
void tamanho_vetor();
void imprimir_vetor();

// Menus:
void menu_ordenacao();
void menu_busca();

// Métodos - Ordenação:
void insertion_sort(int inicio, int fim);
void selection_sort(int inicio, int fim);
void imprimir_ins_sel(int inicio, int fim, int k, int l, int k_moveu, int inicial, int troca);

void quicksort(int esquerda, int direita);
void quicksort_hibrido(int esquerda, int direita);
int particiona(int esquerda, int direita);
void swap(int i, int j);
void imprimir_quicksort(int esquerda, int direita, int i, int j, int pivo, int troca, int vetor_inteiro, int caminhou_i);

// Métodos - Busca:
int busca_sequencial(int esquerda, int direita, int valor);
int busca_binaria(int primeiro, int ultimo, int valor, int passo);
void imprimir_busca_binaria(int primeiro, int ultimo, int meio, int *passo);


int main() {
    int opcao = 0;
	
    criar_vetor_aleatorio();
	
    while(opcao >= 0) {
        limpar_tela();
        imprimir_vetor();
        printf("\n\n*** MENU PRINCIPAL ***\n");
        printf("\nEscolha uma opcao:\n");
        printf("\n1. Gerar novo vetor aleatorio");
        printf("\n2. Gerar novo vetor manual");
        printf("\n3. Menu - Ordenacao");
        printf("\n4. Menu - Busca");
        printf("\nn. Sair");
        printf("\n\nOpcao: ");
        scanf("%d", &opcao);
        switch(opcao) {
            case 1:
                criar_vetor_aleatorio();
            break;

            case 2:
                criar_vetor_manual();
            break;
            
            case 3:
                menu_ordenacao();
            break;
            
            case 4:
                menu_busca();
            break;

            default:
                opcao = -1;

        } // Fecha switch

    } // Fecha while
	
    printf("\n");
    return(0);
}

void menu_ordenacao() {
    int opcao = 0;
	
    while(opcao >= 0) {
        limpar_tela();
        imprimir_vetor();
        printf("\n\n*** MENU - ORDENACAO ***\n");
        printf("\nEscolha uma opcao:\n");
        printf("\n1. Insertion Sort");
        printf("\n2. Selection Sort");
        printf("\n3. Quick Sort");
        printf("\n4. Quick Sort (Hibrido)");
        printf("\nn. Voltar");
        printf("\n\nOpcao: ");
        scanf("%d", &opcao);
        switch(opcao) {
            case 1:
                quick = 0;
                insertion_sort(0, tamanho-1);
                ordenado = 1; // Função Geral do Programa: Vetor Ordenado
            break;
			
            case 2:
                selection_sort(0, tamanho-1);
                ordenado = 1; // Função Geral do Programa: Vetor Ordenado
            break;
			
            case 3:
                quicksort(0, tamanho-1);
                ordenado = 1; // Função Geral do Programa: Vetor Ordenado
            break;
			
            case 4:
                quicksort_hibrido(0, tamanho-1);
                ordenado = 1; // Função Geral do Programa: Vetor Ordenado
            break;
		
            default:
                opcao = -1;
			
        } // Fecha switch

    } // Fecha while
}

void menu_busca() {
    int opcao = 0;
    int valor, posicao;
	
    while(opcao >= 0) {
        limpar_tela();
        imprimir_vetor();
        printf("\n\n*** MENU - BUSCA ***\n");
        printf("\nEscolha uma opcao:\n");
        printf("\n1. Busca Sequencial");
        printf("\n2. Busca Binaria");
        printf("\nn. Voltar");
        printf("\n\nOpcao: ");
        scanf("%d", &opcao);
        if(opcao == 1 || opcao == 2) {
            printf("\nDigite o valor a ser encontrado: ");
            scanf("%d", &valor);
            printf("\n");
        }
        switch(opcao) {
            case 1:
                posicao = busca_sequencial(0, tamanho-1, valor);
                if(posicao == -1) {
                    printf("Valor nao encontrado\n\n");
                }
                else {
                    printf("Valor esta na posicao: %d\n\n", posicao);
                }
                pausar();
            break;
			
            case 2:
                if(ordenado == 0) {
                    printf("Vetor nao ordenado. Ordene-o primeiro.\n\n");
                }
                else {
                    posicao = busca_binaria(0, tamanho-1, valor, 0);
                    if(posicao == -1) {
                        printf("\n\nValor nao encontrado\n\n");
                    }
                    else {
                        printf("\n\nValor esta na posicao: %d\n\n", posicao);
                    }
                }
                pausar();
            break;
		
            default:
                opcao = -1;
			
        } // Fecha switch

    } // Fecha while
}

/* MÉTODOS - VETOR */

void criar_vetor_aleatorio() {
    int k, l, valor, existe;
	
    tamanho_vetor();
	
    for(k = 0 ; k < tamanho ; k++) {
        vetor[k] = 0;
    }
	
    srand(time(0));
	
    for(k = 0 ; k < tamanho ; k++) {
        existe = 0;
        valor = rand()%tamanho + 1;
        for(l = 0 ; l < tamanho ; l++) {
            if(vetor[l] == valor) {
                existe = 1;
            }
        }
        if(existe) {
            k--;
        }
        else {
            vetor[k] = valor;
        }
    }
	
    ordenado = 0;
}

void criar_vetor_manual() {
    int k;
	
    tamanho_vetor();
	
    for(k = 0 ; k < tamanho ; k++) {
        printf("\nDigite o valor da posicao %d de %d: ", k+1, tamanho);
        scanf("%d", &vetor[k]);
    }
	
    ordenado = 0;
	
    printf("\nVetor criado!\n\n");
    pausar();
}

void tamanho_vetor() {
    limpar_tela();
    printf("\nDigite o tamanho do Vetor: ");
    scanf("%d", &tamanho);
	
    if(tamanho < 10) {
        printf("\nAviso: Tamanho minimo = 10.");
        tamanho = 10;
    }
    else if(tamanho > 30) {
        printf("\nAviso: Tamanho maximo = 30.");
        tamanho = 30;
    }
    else {
        printf("\nTamanho do vetor: %d", tamanho);
    }
	
    printf("\n\n");
    pausar();
}

void imprimir_vetor() {
    int k;
	
    printf("\nVetor: ");
    for(k = 0 ; k < tamanho ; k++) {
        printf("%d ", vetor[k]);
    }
}


/*  MÉTODOS - ORDENAÇÃO *

    OBS: CONSIDERA-SE O VETOR COMO VARIÁVEL GLOBAL EM CADA MÉTODO */

void insertion_sort(int inicio, int fim) {
    int k, l;
    int aux;
	
    for(k = inicio+1 ; k <= fim ; k++) {
        aux = vetor[k]; // Armazena o valor da posição atual
        
        imprimir_ins_sel(inicio, fim, k, 0, 1, 1, 0); // Apenas imprime na tela, não faz parte do código original
		
        /*  l = k-1 / l--: Começa a voltar as posições do vetor a partir de uma antes da posição atual
            l >= inicio: Volta até a posição inicial
            vetor[l] > aux: O valor da posição atual é maior que o inicial de k */
        for(l = k-1 ; l >= inicio && vetor[l] > aux; l--) {
        
            /*  Cada elemento é "avançado" uma posição até a condição não ser mais válida e
                aux ser maior ou igual ao vetor[l]. A partir daí, l para de ser decrementado */
            vetor[l+1] = vetor[l];
            
            imprimir_ins_sel(inicio, fim, k, l, 0, 1, 0); // Apenas imprime na tela, não faz parte do código original
        }
		
        /* Valor de l estará sempre um a menos que o de k, independente de ter caído nas condições do loop */
        vetor[l+1] = aux;
        
        imprimir_ins_sel(inicio, fim, k, l, 0, 1, 1); // Apenas imprime na tela, não faz parte do código original
                
    } // Fecha Loop k
	
    printf("\n");
    pausar();
}

void selection_sort(int inicio, int fim) {
    int k, l;
    int menor, aux;
	
    for(k = inicio ; k < fim ; k++) {
        menor = k; // Assume-se que o menor valor está na posição k
        
        imprimir_ins_sel(inicio, fim, k, 0, 1, 0, 0); // Apenas imprime na tela, não faz parte do código original
		
        /* Percorre o vetor a partir de uma posição a mais que k: */
        for(l = k+1 ; l <= fim ; l++) {
		
            /*  Se o valor é menor que o que está na posição "menor":
                (A posição "menor" começa em "k" mas se houve uma troca, é do último
                menor valor encontrado na última posição l) */
            if(vetor[l] < vetor[menor]) {
                menor = l;
            }
            
            imprimir_ins_sel(inicio, fim, k, l, 0, 0, 0); // Apenas imprime na tela, não faz parte do código original
        }
		
        /* Se encontrou um valor menor que o da posição k, troca: */
        if(k != menor) {
            swap(k, menor);
            
            imprimir_ins_sel(inicio, fim, k, l, 0, 1, 1); // Apenas imprime na tela, não faz parte do código original
        }
    }
	
    printf("\n");
    pausar();
}

void quicksort(int esquerda, int direita) {
    int index = particiona(esquerda, direita);
    if(esquerda < index - 1) {
        quicksort(esquerda, index - 1);	
    }
    if(index < direita) {
        quicksort(index, direita);
    }
}

/*  Para sub-vetores muito pequenos, é melhor utilizar o Insertion Sort.
    O quão pequeno pode depender da máquina em questão. O exemplo usa
    um tamanho padrão "menor que 5". */
void quicksort_hibrido(int esquerda, int direita) {
    if(direita - esquerda < 5) {
        printf("\nSub-Vetor pequeno, ordenando via Insertion Sort...\n\n");
        quick = 1; // Não faz parte do código, controle global de impressão de tela
        insertion_sort(esquerda, direita);
    }
    else {
        int index = particiona(esquerda, direita);
        if(esquerda < index - 1) {
            quicksort_hibrido(esquerda, index - 1);	
        }
        if(index < direita) {
            quicksort_hibrido(index, direita);
        }	
    }
}

/* Função Principal do Quicksort */
int particiona(int esquerda, int direita) {
    int i = esquerda, j = direita;
	
    /*  Escolha do Pivô: Existem outros métodos como Mediana de 3,
        porém o valor do meio é simples e eficaz: */
    int pivo = vetor[(esquerda + direita)/2];

    imprimir_quicksort(esquerda, direita, i, j, pivo, 0, 1, 0); // Apenas imprime na tela, não faz parte do código original
    while (i <= j) {
	
        /* O valor de "i", que parte da esquerda, é incrementado enquanto vetor[i] for menor que o pivô: */
        while(vetor[i] < pivo) {
            i++;
            imprimir_quicksort(esquerda, direita, i, j, pivo, 0, 0, 1); // Apenas imprime na tela, não faz parte do código original
        }
		
        /* O valor de "j", que parte da direita, é decrementado enquanto vetor[j] for maior que o pivô: */
        while(vetor[j] > pivo) {
            j--;
            imprimir_quicksort(esquerda, direita, i, j, pivo, 0, 0, 0); // Apenas imprime na tela, não faz parte do código original
        }
		
        /* Troca os valores caso "i" seja menor ou igual a "j" */
        if(i <= j) {
            swap(i, j);
            imprimir_quicksort(esquerda, direita, i, j, pivo, 1, 0, 0); // Apenas imprime na tela, não faz parte do código original
            i++; // Faz um incremento adicional
            imprimir_quicksort(esquerda, direita, i, j, pivo, 0, 0, 1); // Apenas imprime na tela, não faz parte do código original
            j--; // Faz um decremento adicional
            imprimir_quicksort(esquerda, direita, i, j, pivo, 0, 0, 0); // Apenas imprime na tela, não faz parte do código original
        }
    }

return(i);
}

/* Função de Troca */

void swap(int i, int j) {
    int tmp;
    tmp = vetor[i];
    vetor[i] = vetor[j];
    vetor[j] = tmp;
}


/* MÉTODOS - EXIBIR PROCESSO DE ORDENAÇÃO NA TELA */

void imprimir_ins_sel(int inicio, int fim, int k, int l, int k_moveu, int insertion, int troca) {
    int cont;
    
    if(k_moveu) {
        if(insertion && k == inicio+1) {
            if(!quick) {
                limpar_tela();
            }
            else {
                pausar();
                printf("\n");
            }
        }
        else if(!insertion && k == inicio) {
            limpar_tela();
        }
        else {
            printf("\n");
            pausar();
            limpar_tela();
        }
        printf("Vetor: ");
        for(cont = inicio ; cont <= fim ; cont++) {
           if(k == cont) {
               printf(" | %d | ", vetor[cont]);
           }
           else {
               printf(" %d ", vetor[cont]);
           }
        }
        printf("\n");
    }
    else {
        if(!troca) {
            printf("Vetor: ");
        }
        else {
            printf("\nVetor: ");
        }
        for(cont = inicio ; cont <= fim ; cont++) {
           if(k == cont) {
               printf(" | %d | ", vetor[cont]);
           }
           else if(l == cont && !troca) {
                printf(" < %d > ", vetor[cont]);
           }
           else {
               printf(" %d ", vetor[cont]);
           }
        }
    }
    printf("\n");
}

void imprimir_quicksort(int esquerda, int direita, int i, int j, int pivo, int troca, int vetor_inteiro, int caminhou_i) {
    int k;
    if(troca) {
        printf("\nPIVO = %d | Sub-Vetor: ", pivo);
        for(k = esquerda ; k <= direita ; k++) {
            if(k == i || k == j) {
                printf("<%d> ", vetor[k]);
            }
            else {
                printf("%d ", vetor[k]);
            }
        }
    }
    else if(vetor_inteiro) {
        limpar_tela();
        printf("\nPIVO = %d | Vetor Inteiro: ", pivo);
        for(k = 0 ; k < tamanho ; k++) {
            if(k == i || k == j) {
                printf("[%d] ", vetor[k]);
            }
            else if(vetor[k] == pivo) {
                printf("{%d} ", vetor[k]);
            }
            else {
                printf("%d ", vetor[k]);
            }
        }
    }
    else if(caminhou_i) {
        printf("\ni = %d", vetor[i]);
        printf("\nPIVO = %d | Sub-Vetor: ", pivo);
        for(k = esquerda ; k<= direita ; k++) {
            if(k == i || k == j) {
                printf("[%d] ", vetor[k]);
            }
            else {
                printf("%d ", vetor[k]);
            }
        }
    }
    else {
        printf("\nj = %d", vetor[j]);
        printf("\nPIVO = %d | Sub-Vetor: ", pivo);
        for(k = esquerda ; k<= direita ; k++) {
            if(k == i || k == j) {
                printf("[%d] ", vetor[k]);
            }
            else {
                printf("%d ", vetor[k]);
            }
        }
    }
	
    printf("\n");
    pausar();
    printf("\n");
}


/* MÉTODOS - BUSCA */

int busca_sequencial(int esquerda, int direita, int valor) {
    int k, posicao = -1;
	
    printf("Busca Sequencial: ");
    for(k = esquerda ; k <= direita ; k++) {
        if(vetor[k] == valor) {
            posicao = k;
            printf(" | %d | ", vetor[k]);
            break;
        }
        else {
            printf(" %d ", vetor[k]);
        }
    }
    printf("\n\n");
    pausar();
    printf("\n");
	
    return(posicao);
}


int busca_binaria(int primeiro, int ultimo, int valor, int passo) {
    int meio;

    while(primeiro <= ultimo) {
        /* Calcula o valor do meio: */
        meio = (primeiro+ultimo)/2;
		
        imprimir_busca_binaria(primeiro, ultimo, meio, &passo); // Apenas exibe o sub-vetor, não faz parte de um código de busca binária
		
        if(valor == vetor[meio])
            /* Se encontrou o valor na posição do meio, retorna ele: */
            return(meio); 
        else {
            if(valor < vetor[meio])
                return(busca_binaria(primeiro, meio-1, valor, passo)); // Recursiva para um valor menor que o do meio
            else if(valor > vetor[meio])
                return(busca_binaria(meio+1, ultimo, valor, passo)); // Recursiva para um valor maior que o do meio
        }
    }

return(-1); // Só irá retornar -1 se não encontrar o valor
}


/* Exibir Busca Binária na Tela: */
void imprimir_busca_binaria(int primeiro, int ultimo, int meio, int *passo) {
    int k;

    *passo = *passo + 1;

    printf("\nPasso %d - Sub-vetor: ", *passo);

    for (k = primeiro ; k <= ultimo ; k++) {
        if(k == meio)
            printf("| %d | ", vetor[k]);
        else
            printf("%d ", vetor[k]);
    }
}